/* Copyright (C) 1997-2005, Antony L Hosking.
 * All rights reserved.  */
package PPC;

import java.util.*;
import Translate.Temp;
import Translate.Temp.*;
import Translate.Tree.*;
import Translate.Tree.Exp.*;
import Translate.Tree.Stm.*;

/**
 * Represents PowerPC stack frames. <tt>
 * <P>
 * ppc stack frames look like this after procedure prolog has
 * been executed:
 *
 * Higher address:
 *			.........
 *		+-------------------------------+
 * 		| caller's LR			|
 *		+-------------------------------+
 * 		| caller's CR			|
 *		+-------------------------------+
 * Caller's SP->| caller's caller's sp		|  ^^ Caller's Frame ^^
 *		+===============================+  vv Callee's Frame vv
 *		|	Save Area for		| FPF 31
 *			..........
 *		| 	Caller's FPF's		| FPF n
 *		+-------------------------------+
 *		|	Save Area for		| GRF 31
 *			..........
 *		| 	Caller's GRF's		| GRF n
 *		+-------------------------------+
 *		|	alignment pad		|
 *			............
 *		|	(if necessary)		|
 *		+-------------------------------+
 *		|	Local			|
 *			........
 *		| 	Variables		|
 *		+-------------------------------+
 * SP + X ->	| aN for FUTURE call		|
 *		+-------------------------------+
 *			..........
 *		+-------------------------------+
 * SP + 28 ->	| a1 for FUTURE call		|
 *		+-------------------------------+
 * SP + 24 ->	| a0 for FUTURE call		|
 *		+-------------------------------+
 * SP + 20 ->	| caller's TOC			|
 *		+-------------------------------+
 * SP + 16 ->	| reserved			|
 *		+-------------------------------+
 * SP + 12 ->	| reserved			|
 *		+-------------------------------+
 * SP + 8 ->	| LR callee-save for FUTURE call|
 *		+-------------------------------+
 * SP + 4 ->	| CR callee-save for FUTURE call|
 *		+-------------------------------+
 * SP ->	| caller's sp			|
 *		+===============================+
 * Lower address:
 * </tt>
 * 
 * NOTE: All state with the exception of LR and CR are saved in the callee's
 * frame. LR and CR are saved in the CALLER'S FRAME.
 * 
 * ALSO NOTE: Args to the callee are found in the caller's frame.
 */
public abstract class Frame extends Translate.Frame {
    private class InFrame extends Translate.Frame.Access {
        int offset;

        InFrame(int o) {
            offset = o;
        }

        public Exp exp() {
            return new MEM(new TEMP(FP), new CONST(offset));
        }

        public String toString() {
            return "FP+" + offset;
        }
    }

    private class InReg extends Translate.Frame.Access {
        Temp temp;

        InReg(Temp t) {
            temp = t;
        }

        public Exp exp() {
            return new TEMP(temp);
        }

        public String toString() {
            return temp.toString();
        }
    }

    private Frame(Label n) {
        super(n);
    }

    static final int wordSize = 4;

    public int wordSize() {
        return wordSize;
    }

    static final int linkageSize = 5 * wordSize;

    private LinkedList<Access> actuals = new LinkedList<Access>();

    public Access allocFormal(Temp t) {
        Access a;
        int index = formals.size();
        if (index < argRegs.length) {
            actuals.add(new InReg(argRegs[index]));
            if (t == null)
                a = new InFrame(index * wordSize + linkageSize);
            else
                a = new InReg(t);
        } else {
            a = new InFrame(index * wordSize + linkageSize);
            actuals.add(a);
            if (t != null)
                a = new InReg(t);
        }
        formals.add(a);
        return a;
    }

    private int numLocals = 0;

    public Access allocLocal(Temp t) {
        if (t != null)
            return new InReg(t);
        int offset = ++numLocals;
        return new InFrame(-(offset * wordSize));
    }

    abstract Temp reg(int i);

    final Temp ZT = reg(0); // architecturally 0 for mem refs!
    // real reg other inst
    // caller-saved
    final Temp SP = reg(1); // stack pointer, callee-saved
    final Temp TOC = reg(2); // tbl of contents, callee-saved,
    // except on Mac OS X caller-saved
    final Temp A0 = reg(3); // arg 0, return value 0,
    // caller-saved
    final Temp A1 = reg(4); // arg 1, return value 1,
    // caller-saved
    final Temp A2 = reg(5); // ...
    final Temp A3 = reg(6); // ...
    final Temp A4 = reg(7); // ...
    final Temp A5 = reg(8); // ...
    final Temp A6 = reg(9); // ...
    final Temp A7 = reg(10); // ...
    final Temp EP = reg(11); // environment ptr, caller-saved
    final Temp AT = reg(12); // assembler temp, caller-saved
    final Temp S17 = reg(13); // callee-saved 17 on Mac OS X;
    // small data area pointer on Linux
    final Temp S16 = reg(14); // callee-saved 16
    final Temp S15 = reg(15); // ...
    final Temp S14 = reg(16); // ...
    final Temp S13 = reg(17); // ...
    final Temp S12 = reg(18); // ...
    final Temp S11 = reg(19); // ...
    final Temp S10 = reg(20); // ...
    final Temp S9 = reg(21); // ...
    final Temp S8 = reg(22); // ...
    final Temp S7 = reg(23); // ...
    final Temp S6 = reg(24); // ...
    final Temp S5 = reg(25); // ...
    final Temp S4 = reg(26); // ...
    final Temp S3 = reg(27); // ...
    final Temp S2 = reg(28); // ...
    final Temp S1 = reg(29); // ...
    final Temp S0 = reg(30); // callee-saved 0
    final Temp FP = reg(31); // frame-pointer, callee-saved

    // Register lists: must not overlap and must include every register that
    // might show up in code
    final Temp[]
    // registers dedicated to special purposes
            specialRegs = { ZT, SP, TOC, EP, AT, S17 },
            // registers to pass outgoing arguments
            argRegs = { A0, A1, A2, A3, A4, A5, A6, A7 },
            // registers that a callee must preserve for its caller
            calleeSaves = { FP, S0, S1, S2, S3, S4, S5, S6, S7, S8, S9, S10,
                    S11, S12, S13, S14, S15, S16 },
            // registers that a callee may use without preserving
            callerSaves = {};

    private Temp[] registers =
        new Temp[callerSaves.length + argRegs.length + calleeSaves.length
            + specialRegs.length];
    {
        int i = 0;
        for (Temp t : callerSaves)
            registers[i++] = t;
        for (Temp t : argRegs)
            registers[i++] = t;
        for (Temp t : calleeSaves)
            registers[i++] = t;
        for (Temp t : specialRegs)
            registers[i++] = t;
    }

    public Temp[] registers() {
        return registers;
    }

    public Temp RV = null;

    public Exp RV() {
        if (RV == null)
            RV = A0;
        return new TEMP(RV);
    }

    public String string(Label lab, String string) {
        int length = string.length();
        String lit = "";
        for (int i = 0; i < length; i++) {
            char c = string.charAt(i);
            switch (c) {
            case '\b':
                lit += "\\b";
                break;
            case '\t':
                lit += "\\t";
                break;
            case '\n':
                lit += "\\n";
                break;
            case '\f':
                lit += "\\f";
                break;
            case '\r':
                lit += "\\r";
                break;
            case '\"':
                lit += "\\\"";
                break;
            case '\\':
                lit += "\\\\";
                break;
            default:
                if (c < ' ' || c > '~') {
                    int v = (int) c;
                    lit += "\\" + ((v >> 6) & 7) + ((v >> 3) & 7) + (v & 7);
                } else
                    lit += c;
                break;
            }
        }
        return "\t.data\n\t.align 2\n" + lab + ":\t.asciz\t\"" + lit + "\"";
    }

    public String record(Label lab, int words) {
        String result = "\t.data\n\t.align 2\n" + lab + ":\n";
        if (words > 0)
            result += "\t.space " + words * wordSize + ",0";
        return result;
    }

    public String vtable(Label lab, Collection<Label> values) {
        String result = "\t.data\n\t.align 2\n" + lab + ":";
        for (Label l : values)
            result += "\n\t.long " + l;
        return result;
    }

    private Label badPtr = new Label();

    public Label badPtr() {
        return badPtr;
    }

    private Label badSub = new Label();

    public Label badSub() {
        return badSub;
    }

    // Registers defined by a call
    final Temp[] callDefs = new Temp[argRegs.length + callerSaves.length];
    {
        int i = 0;
        for (Temp t : argRegs)
            callDefs[i++] = t;
        for (Temp t : callerSaves)
            callDefs[i++] = t;
    }

    abstract String lo16(String s);

    abstract String ha16(String s);

    abstract String hi16(String s);

    private void saveArgs(Iterator<Access> formals, Iterator<Access> actuals,
            LinkedList<Stm> body) {
        if (!formals.hasNext() || !actuals.hasNext())
            return;
        Access formal = formals.next();
        Access actual = actuals.next();
        saveArgs(formals, actuals, body);
        if (formal != actual)
            body.addFirst(new MOVE(formal.exp(), actual.exp()));
    }

    public void procEntryExit1(LinkedList<Stm> body) {
        saveArgs(formals.iterator(), actuals.iterator(), body);
    }

    protected LinkedList<String> picsymbols = new LinkedList<String>();
    static final int redZoneSize = 224;
    static final int stackIncr = 16;

    public static class Darwin extends Frame {
        public Frame newFrame(String name) {
            return new Darwin(name);
        }

        private static Frame mainFrame = null;

        public Frame mainFrame() {
            if (mainFrame == null)
                mainFrame = new Darwin("_main");
            return mainFrame;
        }

        public Darwin() {
            super(null);
        }

        private Darwin(String n) {
            super(Label.get(n));
        }

        private static final Temp[] regs =
            new Temp[] { new Temp("r0"), new Temp("r1"), new Temp("r2"),
                    new Temp("r3"), new Temp("r4"), new Temp("r5"),
                    new Temp("r6"), new Temp("r7"), new Temp("r8"),
                    new Temp("r9"), new Temp("r10"), new Temp("r11"),
                    new Temp("r12"), new Temp("r13"), new Temp("r14"),
                    new Temp("r15"), new Temp("r16"), new Temp("r17"),
                    new Temp("r18"), new Temp("r19"), new Temp("r20"),
                    new Temp("r21"), new Temp("r22"), new Temp("r23"),
                    new Temp("r24"), new Temp("r25"), new Temp("r26"),
                    new Temp("r27"), new Temp("r28"), new Temp("r29"),
                    new Temp("r30"), new Temp("r31") };

        Temp reg(int i) {
            return regs[i];
        }

        private static HashSet<String> externs = new HashSet<String>();

        public Exp external(String s) {
            Label l = Label.get("L_" + s + "$stub");
            if (externs.add(s)) {
                String out = "";
                out +=
                    ".section __TEXT,__picsymbolstub1,symbol_stubs,pure_instructions,32\n";
                out += "\t.align 2\n";
                out += "L_" + s + "$stub:\n";
                out += "\t.indirect_symbol _" + s + "\n";
                out += "\tmflr r0\n";
                out += "\tbcl 20,31,L0$_" + s + "\n";
                out += "L0$_" + s + ":\n";
                out += "\tmflr r11\n";
                out +=
                    "\taddis r11,r11,ha16(L_" + s + "$lazy_ptr-L0$_" + s
                        + ")\n";
                out += "\tmtlr r0\n";
                out +=
                    "\tlwzu r12,lo16(L_" + s + "$lazy_ptr-L0$_" + s
                        + ")(r11)\n";
                out += "\tmtctr r12\n";
                out += "\tbctr\n";
                out += "\t.data\n";
                out += "\t.align 2\n";
                out += "\t.lazy_symbol_pointer\n";
                out += "L_" + s + "$lazy_ptr:\n";
                out += "\t.indirect_symbol _" + s + "\n";
                out += "\t.long dyld_stub_binding_helper";
                picsymbols.add(out);
            }
            return new NAME(l);
        }

        String lo16(String s) {
            return "lo16(" + s + ")";
        }

        String ha16(String s) {
            return "ha16(" + s + ")";
        }

        String hi16(String s) {
            return "hi16(" + s + ")";
        }
    }

    public static class Linux extends Frame {
        public Frame newFrame(String name) {
            return new Linux(name);
        }

        private static Frame mainFrame = null;

        public Frame mainFrame() {
            if (mainFrame == null)
                mainFrame = new Darwin("_main");
            return mainFrame;
        }

        public Linux() {
            super(null);
        }

        private Linux(String n) {
            super(Label.get(n));
        }

        private static final Temp[] regs =
            new Temp[] { new Temp("0"), new Temp("1"), new Temp("2"),
                    new Temp("3"), new Temp("4"), new Temp("5"), new Temp("6"),
                    new Temp("7"), new Temp("8"), new Temp("9"),
                    new Temp("10"), new Temp("11"), new Temp("12"),
                    new Temp("13"), new Temp("14"), new Temp("15"),
                    new Temp("16"), new Temp("17"), new Temp("18"),
                    new Temp("19"), new Temp("20"), new Temp("21"),
                    new Temp("22"), new Temp("23"), new Temp("24"),
                    new Temp("25"), new Temp("26"), new Temp("27"),
                    new Temp("28"), new Temp("29"), new Temp("30"),
                    new Temp("31") };

        Temp reg(int i) {
            return regs[i];
        }

        public Exp external(String s) {
            return new NAME(Label.get(s));
        }

        String lo16(String s) {
            return s + "@l";
        }

        String ha16(String s) {
            return s + "@ha";
        }

        String hi16(String s) {
            return s + "@h";
        }
    }

    private static Temp[] Temps(Temp... a) {
        return a;
    }

    private static Assem.Instr.OPER OPER(String a, Temp[] d, Temp[] s) {
        return new Assem.Instr.OPER(a, d, s);
    }

    private static Assem.Instr.OPER OPER(String a) {
        return OPER(a, Temps(), Temps());
    }

    private Temp[] returnSink = specialRegs;

    public Translate.Tree.Visitor<LinkedList<Assem.Instr>, Temp> codegen() {
        return new Codegen(this);
    }

    public void procEntryExit2(LinkedList<Assem.Instr> insns) {
        if (RV != null) {
            returnSink = new Temp[specialRegs.length + 1];
            int i = 0;
            for (Temp t : specialRegs)
                returnSink[i++] = t;
            returnSink[i] = RV;
        }
        insns.addLast(OPER("#\treturnSink", Temps(), returnSink));
    }

    public void procEntryExit3(LinkedList<Assem.Instr> insns, Temp.Map map) {
        HashSet<Temp> defs = new HashSet<Temp>();
        for (Assem.Instr insn : insns) {
            for (Temp t : insn.def)
                defs.add(map.get(t));
        }

        int grfSaved = 0;
        for (int i = 0; i < calleeSaves.length; i++)
            if (defs.contains(calleeSaves[i]))
                grfSaved = i + 1;

        int frameSize = (numLocals + grfSaved) * wordSize;

        if (maxArgsOut >= 0 || numLocals > 0 || frameSize > redZoneSize) {
            frameSize += linkageSize;
            if (maxArgsOut < 8)
                maxArgsOut = 8;
            frameSize += maxArgsOut * wordSize;
            frameSize = (frameSize + stackIncr - 1) / stackIncr * stackIncr;
        } else
            frameSize = 0;

        if (frameSize != 0) {
            insns.addFirst(OPER("\tstwu `d0,-__framesize(`s0)", Temps(SP),
                                Temps(SP)));
            insns.addLast(OPER("\taddi `d0,`s0,__framesize", Temps(SP),
                               Temps(SP)));
        }

        int offset = -frameSize;
        if (grfSaved > 0) {
            Temp[] u = new Temp[grfSaved + 1];
            Temp[] d = new Temp[grfSaved];
            for (int i = 0; i < grfSaved; i++)
                d[i] = u[i] = calleeSaves[i];
            u[grfSaved] = SP;
            insns.addFirst(OPER("\tstmw " + calleeSaves[grfSaved - 1] + ","
                + offset + "(" + SP + ")", Temps(), u));
            insns.addLast(OPER("\tlmw " + calleeSaves[grfSaved - 1] + ","
                + offset + "(" + SP + ")", d, Temps(SP)));
        }

        if (frameSize != 0) {
            // save/restore return address
            insns.addFirst(OPER("\tstw `s0,8(`s1)", Temps(), Temps(ZT, SP)));
            insns.addLast(OPER("\tlwz `d0,8(`s0)", Temps(ZT), Temps(SP)));

            // save/restore link register
            insns.addFirst(OPER("\tmflr `d0", Temps(ZT), Temps()));
            insns.addLast(OPER("\tmtlr `s0", Temps(), Temps(ZT)));
        }

        insns.addLast(OPER("\tblr", Temps(), returnSink));

        insns.addFirst(OPER("\t.text\n\t.align 2\n" + name + ":\n"
            + "__framesize=" + frameSize));
        if (this == mainFrame())
            insns.addFirst(OPER("\t.globl " + name));

        if (badPtr != null)
            insns.addLast(OPER(badPtr.toString() + ":\n\tbl badPtr"));
        if (badSub != null)
            insns.addLast(OPER(badSub.toString() + ":\n\tbl badSub"));

        for (String s : picsymbols)
            insns.addLast(OPER(s));
    }
}
